<?php
/**
 * 有向无圈图 DAG
 */
class DirectedAcyclicGraph
{
    /**
     * @var Vertex[] $list 顶点列表
     */
    public $list=[];
    /**
     * 使用邻接表初始化DAG
     * 生成的图是无权的
     * @param array[] $list 邻接表
     */
    public function initWithAdjacencyList($list=[])
    {
        $this->list=[];
        foreach($list as $vertex_no => $adjacent){
            $vertex=new Vertex();
            $vertex->no=$vertex_no;
            $this->list[$vertex_no]=$vertex;
        }
        foreach($list as $vertex_no => $adjacent){
            $current_vertex=$this->list[$vertex_no];
            foreach($adjacent as $adjacent_vertex_no){
                if(isset($this->list[$adjacent_vertex_no])){
                    $current_vertex->adjacent[]=$this->list[$adjacent_vertex_no];
                }
                else{
                    throw new Exception("顶点`$vertex_no`邻接到不存在的顶点`$adjacent_vertex_no`");
                }
            }
        }
    }
    /**
     * 使用邻接矩阵初始化DAG
     * 生成的图是加权的
     * 可以省略不相接的顶点
     * @param array[] $matrix 邻接矩阵
     */
    public function initWithAdjacencyMatrix($matrix)
    {
        $this->list=[];
        foreach($matrix as $vertex_no => $adjacent){
            $vertex=new Vertex();
            $vertex->no=$vertex_no;
            $this->list[$vertex_no]=$vertex;
        }
        foreach($matrix as $vertex_no => $adjacent){
            $current_vertex=$this->list[$vertex_no];
            foreach($adjacent as $adjacent_no => $adjacent_cost){
                if(isset($this->list[$adjacent_no])){
                    $current_vertex->adjacent[]=$this->list[$adjacent_no];
                    $current_vertex->adjacentDistance[]=$adjacent_cost;
                }
                else{
                    throw new Exception("顶点`$vertex_no`邻接到不存在的顶点`$adjacent_no`");
                }
            }
        }
    }
    /**
     * 重新计算所有顶点的入度
     * @return void
     */
    protected function initVertexIndegree()
    {
        foreach($this->list as $vertex){
            $vertex->indegree=0;
        }
        foreach($this->list as $vertex){
            foreach($vertex->adjacent as $adjacent_vertex){
                $adjacent_vertex->indegree++;
            }
        }
    }
    /**
     * 获取拓扑排序后的列表
     * 循环的将入度为0的顶点放入序列
     * @return Vertex[]
     */
    public function getTopologySortList()
    {
        $this->initVertexIndegree();
        $sort_list=[];
        $list=$this->list;
        while($list){
            $current_vertex=null;
            foreach($list as $index => $vertex){
                if($vertex->indegree === 0){
                    unset($list[$index]);
                    $current_vertex=$vertex;
                    break;
                }
            }
            if($current_vertex === null){
                throw new Exception("输入的有向图有圈");
            }
            foreach($current_vertex->adjacent as $vertex){
                $vertex->indegree--;
            }
            $sort_list[]=$current_vertex;
        }
        return $sort_list;
    }
    /**
     * 改进拓扑排序算法
     * 每次查找出所有入度为0的顶点放入序列
     * @return Vertex[]
     */
    public function getTopologySortList2()
    {
        $this->initVertexIndegree();
        $sort_list=[];
        $list=$this->list;
        while($list){
            $zero_list=[];
            foreach($list as $index => $vertex){
                if($vertex->indegree === 0){
                    unset($list[$index]);
                    $zero_list[]=$vertex;
                }
            }
            if(!$zero_list){
                throw new Exception("输入的有向图有圈");
            }
            foreach($zero_list as $vertex){
                foreach($vertex->adjacent as $adjacent_vertex){
                    $adjacent_vertex->indegree--;
                }
                $sort_list[]=$vertex;
            }
        }
        return $sort_list;
    }
    /**
     * 计算从一个顶点开始到其他顶点的无权最短路径长
     * @param Vertex $start 起点
     * @return Vertex[]
     */
    public function unweighted($start)
    {
        //为顶点属性设置默认值
        foreach($this->list as $vertex){
            $vertex->know=false;
            $vertex->distance=INF;
            $vertex->previous=null;
        }
        $start->know=true;
        $start->distance=0;
        $count=1;//已知顶点数量
        $dist=0;//当前路径长度
        while($count<count($this->list)){
            foreach($this->list as $vertex){
                if($vertex->know && $vertex->distance===$dist){
                    foreach($vertex->adjacent as $adjacent_vertex){
                        if(!$adjacent_vertex->know){
                            $adjacent_vertex->know=true;
                            $adjacent_vertex->distance=$dist+1;
                            $adjacent_vertex->previous=$vertex;
                            $count++;
                        }
                    }
                }
            }
            $dist++;
        }
        return $this->list;
    }
    /**
     * 递归的更新邻接点的路径长
     * @param Vertex $vertex 顶点
     */
    protected function updateAdjacentVertexDistance($vertex)
    {
        $dist=$vertex->distance+1;
        foreach($vertex->adjacent as $adjacent_vertex){
            if($dist < $adjacent_vertex->distance){
                $adjacent_vertex->previous=$vertex;
                $adjacent_vertex->distance=$dist;
                $this->updateAdjacentVertexDistance($adjacent_vertex);
            }
        }
    }
    /**
     * 以递归的方式计算无权最短路径长
     * @param Vertex $start 起点
     * @return Vertex[]
     */
    public function unweighted2($start)
    {
        //为顶点属性设置默认值
        foreach($this->list as $vertex){
            $vertex->distance=INF;
            $vertex->previous=null;
        }
        $start->distance=0;
        $this->updateAdjacentVertexDistance($start);
        return $this->list;
    }
    
    /**
     * 检查顶点的路径中是否存在圈
     * 当计算无权路径长时，存在圈不影响最短路径长，所以不需要检查
     * 当计算赋权路径长时，已知当前路径时最短路径，则圈很可能是负值圈，会导致死循环
     * @param Vertex $vertex 顶点
     */
    protected function checkCycle($vertex)
    {
        $start=$vertex;
        while($vertex->path){
            $vertex=$vertex->path;
            if($vertex === $start){
                throw new Exception("存在圈");
            }
        }
    }
    /**
     * 使用Dijkstra算法计算赋权路径长
     * @param Vertex $start 起点
     * @return Vertex[]
     */
    public function dijkstra($start)
    {
        foreach($this->list as $vertex){
            $vertex->distance=INF;
            $vertex->know=false;
            $vertex->previous=null;
        }
        $start->distance=0;
        $this->dijkstraUpdateVertex($start);
        $count=1;//已知顶点数量
        while($count<count($this->list)){
            $vertex=$this->getMinUnknowDistanceVertex();
            $this->dijkstraUpdateVertex($vertex);
            $count++;
        }
        return $this->list;
    }
    /**
     * 更新一个顶点为已知并更新相邻顶点的距离
     * @param Vertex $start 起点
     */
    public function dijkstraUpdateVertex($vertex)
    {
        $vertex->know=true;
        foreach($vertex->adjacent as $index => $adjacent_vertex){
            if($adjacent_vertex->know === false){
                $distance = isset($vertex->adjacentDistance[$index]) ? $vertex->adjacentDistance[$index] : 1;
                $distance = $vertex->distance + $distance;
                if($distance < $adjacent_vertex->distance){
                    $adjacent_vertex->distance=$distance;
                    $adjacent_vertex->previous=$vertex;
                }
            }
        }
    }
    /**
     * 获取距离最小的未知节点
     * @return Vertex
     */
    public function getMinUnknowDistanceVertex()
    {
        /** @var Vertex $min_unknow_distance_vertex */
        $min_unknow_distance_vertex=null;
        foreach($this->list as $vertex){
            if($vertex->know === false){
                if($min_unknow_distance_vertex === null || $vertex->distance < $min_unknow_distance_vertex->distance){
                    $min_unknow_distance_vertex=$vertex;
                }
            }
        }
        return $min_unknow_distance_vertex;
    }
}
